The present invention relates to the implementation of a computer programming language, and, in particular, the implementation of an object-oriented programming language.
Object-oriented programming languages use classes to describe objects created by the program during execution. Two examples of object-oriented programming languages are Java and C++.
In Java, a class consists of a set of data members. For example, a Java class declaration is in the form:
Class X has four data members, named a, b, c, and d. The execution of a program that contains this class declaration may create a number of instances of this class, also referred to as objects of type X.
The computer executing the program will allocate memory for each object. Eventually, the memory allocated for the created objects may be reclaimed through the xe2x80x9cgarbage collection process,xe2x80x9d when the objects are no longer used by the program. The garbage collection process clears the objects from memory whereby the once allocated memory is now available for use. In other languages without garbage collection, such as C++, unnecessary objects must be explicitly freed or deallocated.
An important component of implementing a computer programming language is selecting a suitable representation of objects, which includes determining how much memory must be allocated for an object of a class and determining where every member of a class will be located. In a straight forward implementation of the language, every object of type X that is created will have the four data members, namely a, b, c, and d. If an integer member is 4 bytes long, for example, an object of type X will use 16 bytes for the data members.
In addition, the object may require more bytes for other purposes. One other such purpose may be for storing a pointer to the description of the class to which it belongs.
For simplicity, defined herein, the size of an object refers to the size (i.e. bytes of memory) required for the data members of the objects.
In conventional object-oriented programming languages, a specific amount of memory (i.e. number of byes) is allocated for each object based on the number of members in each class. The specific amount of memory is allocated regardless of whether the various members which comprise a class are ever used. For example, if a specific member of a class is never used, the program will still allocate the same amount of memory as if the member were used. Consequently, memory is wasted (i.e. not available for use) by the allocation (i.e reservation) of memory for the member never used.
Certain optimized implementations, such as the ones described by Tip et al. (Frank Tip, Jong-Deok Choi, John Field, G. Ramalingam, Slicing class hierarchies in C++, in Proceedings of the Eleventh Annual Conference on Object Oriented Programming Systems, Languages, and Applications, 1996, pp. 179-197), as well as Tip and Sweeney (Frank Tip and Peter Sweeney, Class hierarchy specialization, in Proceedings of the Twelfth Annual Conference on Object Oriented Programming Systems, Languages, and Applications, 1997, pp. 271-285), might eliminate some unused data members from the representation.
For example, if an analysis of the program indicates that the data member xe2x80x9ccxe2x80x9d of objects of type X is never used, then data member xe2x80x9ccxe2x80x9d can be eliminated from all objects of type X. Consequently, removing member xe2x80x9ccxe2x80x9d can reduce the size of an object of type X from 16 to 12 bytes. The method described by Tip et al. performs this kind of optimization.
However, if the data member xe2x80x9ccxe2x80x9d of some objects of type X is used, and the data member xe2x80x9ccxe2x80x9d of other objects of type X is unused, Tip and Sweeney generate two specialized versions of class X. One first specialized version of class X is for the first collection of objects of type X for which the data member xe2x80x9ccxe2x80x9d is used. A second specialized version of type x is for a second collection of objects of type X for which the data member xe2x80x9ccxe2x80x9d is unused. The data member xe2x80x9ccxe2x80x9d can then be eliminated from the representation of members of the second collection of objects.
While these two methods described by Tip et al. and Tip and Sweeney address the situation when a member of an object is never used, these methods fail to optimize a situation in which various members are used only for part of the lifetime of an object.
For example, often a program has multiple phases Data members xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d of objects of type X might be used only during phase 1 of the program, while data members xe2x80x9ccxe2x80x9d and xe2x80x9cdxe2x80x9d might be used only during phase 2 of the program. The earlier optimizations are not applicable in such a situation because all four members of objects of type X are used. Consequently, no member can be eliminated from the representation of objects of type X.
Thus, the conventional methods fail to provide an optimization method of implementation of objects exploiting the fact that the members of an object are not all in use through out the lifetime of the object.
It is, therefore, an object of the present invention to provide a method and system for optimizing the implementation of objects in which various members representing the object are not all in use throughout the lifetime of the object.
Optimization of the implementation of objects, according to one embodiment, includes statically identifying various collections of objects that may be created during program execution and identifying the lifetimes of the various members of objects belonging to these collections. A second step includes using the lifetime information to generate representations of objects belonging to these collections. Memory requirements are optimized by having members which do not have overlapping lifetimes, share the same memory location.
In addition, the present invention optimizes implementation of objects by breaking objects into multiple fragments. In one embodiment, implementation of an object is represented by several different blocks of memory rather than a single contiguous block of memory as is the case when implementing an object using a conventional method. The various blocks contain a subsets of members that represent an object. Each block of memory used to represent an object is an xe2x80x9cobject fragment.xe2x80x9d Blocks of memory may be allocated and freed independent of the other blocks. As a result, the amount of memory required to represent an object may increase or decrease during the lifetime of the object, as the set of members of the object that are alive changes during program execution.
The invention, in one form thereof, is a method for processing an object-oriented program having objects belonging to a plurality of classes. Each of the plurality of classes have a plurality of members. The method includes identifying a lifetime associated with one or more members of said plurality of members and identifying a set of members in one of the plurality of classes such that no two members in the said set of members have overlapping lifetimes. In one further embodiment, each member of the said set of members is located at the same offset within objects belonging to the one class.
The invention, in another form thereof, is a system for processing an object-oriented program having objects belonging to a plurality of classes. Each of the plurality of classes have a plurality of members. The system includes means for identifying a lifetime associated with one or more members of the plurality of members and identifying a set of members in one of said plurality of classes such that no two members in the set of members have overlapping lifetimes In one further embodiment, each member of the set of members is located at the same offset within objects belonging to the one class.
The invention, in another form thereof, is a system for processing an object-oriented program having objects belonging to a plurality of classes. Each class of the plurality of classes have a plurality of members. The system includes a machine readable recording medium comprising a program for identifying a set of members in one said plurality of classes such that no two members in said set have overlapping lifetimes. In a further embodiment, the program includes creating a representation for objects belonging to the one class in which members of the set of members are located at the same offset within the objects.
The invention, in yet another form thereof, is a system for processing an object-oriented program having objects belonging to a plurality of classes. Each of the plurality of classes have a plurality of members. The system has a memory device containing executable instructions. The executable instructions includes identifying a lifetime associated with one or more members of said plurality of members and identifying a set of members in one of said plurality of classes such that no two members in the said set of members have overlapping lifetimes. In one further embodiment, each member of the said set of members is located at the same offset within objects belonging to said one class.
The invention, in another form thereof, is a method for processing an object-oriented program having a plurality of classes with a plurality of members belonging to each respective class of the plurality of classes. The method includes identifying a set of members in one of said plurality of classes and identifying a lifetime of the set of identified members, wherein the lifetime of the set of members identifies a start point and an end point in the program. The identified members are removed from the one class and a supplemental class is created comprising the identified members. A map data structure is initialized which associates each object of the one class with an object in the supplemental class.
The invention, in yet another form thereof, is a system for processing an object-oriented program having a plurality of classes and having members belonging to each respective class of the plurality of classes. The system includes means for identifying a set of members in one of the plurality of classes. In addition, the system has means for identifying a lifetime of the set of identified members, wherein the lifetime of the set of members identifies a start point and an end point in the program. Further, there is means for removing the identified members from the one class, and for creating a supplemental class comprising the identified members. The system also includes means for initializing a map data structure which associates each object of the one class with an object in the supplemental class.
The invention, in another form thereof, is a system for processing an object-oriented program having a plurality of classes and having members belonging to each respective class of the plurality of classes. The system has a memory device containing executable instructions. The executable instructions includes identifying a set of members in one of said plurality of classes and identifying a lifetime of the set of identified members, wherein the lifetime of the set of members identifies a start point and an end point in the program. The identified members are removing from the said one class and a supplemental class is created comprising the identified members. A map data structure is initialized which associates each object of the one class with an object in the supplemental class. Further, the invention provides a program storage product for storing a program for executing the above method(s).